# 最大子序合(题目链接及动态规划讲解): https://www.zhihu.com/question/23995189
'''
动态规划关键：
1. 满足：重叠子结构，最优子结构
2. 构造状态转移方程

最主要的是能分析出是动态规划题目，或者能将问题巧妙地转化为动态规划解法：看文章讲解
'''

arr =  [-2,1,-3,4,-1,2,1,-5,4]

def maxSubArray(arr):
    """ 动态规划求解 """
    n = len(arr)
    i = 1
    # 存储对应子数组的最大n结尾子序和
    max_l = []  
    max_l.append(arr[0])
    while i < n:
        # 分离指标函数，列出状态转移方程
        max_i = max(max_l[i-1], 0) + arr[i]
        max_l.append(max_i)
        i += 1

    return max(max_l)

a = maxSubArray(arr)
print(a)


# 输入:
# n: 13   k: 2

# 输出:
# 10

# 解释:
# 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

